package JavaLab.Collections;

import java.util.Comparator;
import java.util.RandomAccess;

public class MyCollections {
	public static void sort(MyList list){
        if(list == null) throw new NullPointerException();
        if(list instanceof java.util.RandomAccess){
        	quicksort(list, 0, list.size() - 1);
        }
        else{
        	bubblesort(list);
        }
    }
    
    public static void sort(MyList list, Comparator c){
        if(list == null) throw new NullPointerException();
        if(list instanceof java.util.RandomAccess){
        	quicksort(list, 0, list.size() - 1, c);
        }
        else{
        	bubblesort(list, c);
        }
    }
    
    public static void swap(MyList list, int i, int j){
            Object tempFirst = list.get(i);
            Object tempSecond = list.get(j);
            list.set(i, tempSecond);
            list.set(j, tempFirst);
    }
    
    public static void copy(MyList dest, MyList src){
    	int srcSize = src.size();
    	if(srcSize > dest.size())
    		throw new IndexOutOfBoundsException("Source does not fit in dest");
    	
    	for (int i=0; i<srcSize; i++)
            dest.set(i, src.get(i));
    }
    
    public static void reverse(MyList list){
        for(int i = 1; i <= list.size()/2; i++){
            swap(list, i, list.size() - i + 1);
        }
    }
    
    private static void bubblesort(MyList list, Comparator c) {
        for(int i = 0; i < list.size(); i++){
            for(int j = i; j > 0; j--){
            	if(c.compare(list.get(j), list.get(j-1)) < 0){
            		swap(list, j, j-1);
                    continue;
                }
            	break;
            }
        }
    }
    
    private static void bubblesort(MyList list) {
        for(int i = 0; i < list.size(); i++){
            for(int j = i; j > 0; j--){
            	if(((Comparable)list.get(j)).compareTo(list.get(j-1)) < 0){
            		swap(list, j, j-1);
                    continue;
            	}
                break;
            }
        }
    }
    
    private static void quicksort (MyList list, int p, int r){
        if(p < r){
            int q = partition(list, p, r);
            quicksort(list, p, q-1);
            quicksort(list, q+1, r);   
        }
    }
    
    private static void quicksort (MyList list, int p, int r, Comparator c){
        if(p < r){
            int q = partition(list, p, r);
            quicksort(list, p, q-1);
            quicksort(list, q+1, r);   
        }
    }
    
    private static int partition(MyList list, int p, int r){
        Object x = list.get(r);
        int i = p - 1;
        for(int j = p; j < r; j++){
            if(((Comparable)list.get(j)).compareTo(x) <= 0){
                i++;
                swap(list, i, j);
            }
        }
        swap(list, i+1, r);
        return i + 1;
    }
    
    private static int partition(MyList list, int p, int r, Comparator c){
        Object x = list.get(r);
        int i = p - 1;
        for(int j = p; j < r; j++){
            if(c.compare(list.get(j), x) <= 0){
                i++;
                swap(list, i, j);
            }
        }
        swap(list, i+1, r);
        return i + 1;
    }
    
    public static int binarySearch(RandomAccess list, Object key){
    	MyCollections.sort((MyList)list);
    	return binarySearchRec(list, key, 0, ((MyList)list).size());
    }
    
    private static int binarySearchRec(RandomAccess list, Object key, int l, int r){
    	if(r - l < 2){
    		if(((MyList)list).get(r).equals(key)) return r;
    		else if(((MyList)list).get(l).equals(key)) return l;
    		else {
    			int res = l;
    			if(((Comparable)((MyList)list).get(l)).compareTo(key) < 0) return l;
    			if(((Comparable)((MyList)list).get(r)).compareTo(key) < 0) return r;
    			return r + 1;
    		}
    	}
    	int middle = (l + r) / 2;
    	if(((Comparable)key).compareTo(((MyList)list).get(middle)) < 0){
    		return binarySearchRec(list, key, l, middle);
    	} else{
    		return binarySearchRec(list, key, middle, r);
    	}
    }
}
